/**
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
** \file samarati.cpp
** \version $Id: samarati.cpp 25 2009-10-28 16:17:47Z rigdern $
*/

#include "samarati.h"
#include <numeric>

DistanceVector
samarati(const DataSet& dataSet, unsigned int k, unsigned int maxSup)
{
  unsigned int low, high;
  DistanceVector maximalVector, solution;
  
  maximalVector = dataSet.maximalVector();
  low = 0;
  high = std::accumulate(maximalVector.begin(), maximalVector.end(), 0);
  while (low < high) {
    unsigned int height = (low+high)/2;
    bool reachK = false;
    CombinatorialIterator distanceVectorItr(height, maximalVector);
    
    for (; distanceVectorItr != CombinatorialIterator::end() && !reachK; ++distanceVectorItr) {
      if (dataSet.satisfies(*distanceVectorItr, k, maxSup)) {
        solution = *distanceVectorItr;
        reachK = true;
      }
    }
    
    if (reachK)
      high = height;
    else
      low = height + 1;
  }
  
  return solution;
}